#include "../../tools.h"

class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<bool> dp(nums.size(), false);
        dp.back() = true;

        for(int i = nums.size() - 1; i > -1; --i){
            int bound = i + nums[i] < nums.size() - 1 ? i + nums[i]: nums.size() - 1;
            for(int j = i; j <= bound; ++j){
                if (dp[j]){
                    dp[i] = true;
                    continue;
                }
            }
        }
        return dp[0];
    }
};


int main(int argc, char const *argv[])
{
    vector<int> nums = {3,2,1,0,4};
    
    Solution s;
    cout << s.canJump(nums);
    
    return 0;
}
